最小生成树——数据结构系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

  最小生成树（Minimum Spanning Tree，MST）是无向连通带权图的核心概念，指在包含图中所有顶点的前提下，选取若干条边构成一棵树（无环），且所有边的权值之和最小。它广泛应用于通信网络搭建、道路规划、电路设计等场景，核心解决 “以最小成本连接所有节点” 的问题。本文将详细讲解最小生成树的原理与实现，内容由浅入深，所有代码可直接编译运行。

图结构的实现方式：

1. 邻接矩阵图：是一种使用「一维数组 + 二维数组」存储顶点和边数据的图结构，稠密图中常被采用；
2. 邻接链表图：是一种使用「数组 + 链表」存储顶点和边数据的图结构，稀疏图中常被采用；

一、核心概念

一个有N个顶点的图，边一定是大于等于N-1的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

  最小生成树仅适用于无向连通带权图：无向保证边的双向连通性，连通保证存在生成树，带权是求 “最小” 的前提；若图不连通，仅能求各连通分量的最小生成森林。

1.1 核心性质

• 包含图中全部 n 个顶点，且仅有n-1 条边（树的基本性质：顶点数 = 边数 + 1）；
• 无环（树的本质特征，若有环则可删除一条边保持连通且总权值更小）；
• 总权值是所有满足条件的生成树中最小的；
• 一个图的最小生成树可能不唯一，但总权值一定唯一。

1.2 算法对比与选择

求最小生成树的核心是贪心策略（每一步选择局部最优，最终得到全局最优），最常用的两个算法各有侧重，适配不同场景：

核心差异：Prim 是按顶点扩展，Kruskal 是按边筛选；Kruskal 依赖前文的并查集（判断选边是否形成环），是更易实现且工程中更常用的版本。

二、Kruskal 算法

  按边的权值从小到大依次选择，若选择的边的两个端点不属于同一个连通分量（即选此边不会形成环），则将其加入最小生成树；若形成环则跳过，直到选够n-1 条边（n 为顶点数），此时所有顶点已连通，得到最小生成树。

算法分析：

假设无向连通带权图有n个顶点、m条边：

• 存储所有边：每条边包含「起点 u、终点 v、权值 w」（无向图中 u 和 v 顺序无关）；
• 边排序：将所有边按权值升序排列（贪心的核心，优先选低成本边）；
• 初始化并查集：为n个顶点初始化并查集，每个顶点独立成集；
• 筛选边构建最小生成树：
  1. 遍历排序后的边，依次检查每条边的 u 和 v 是否连通；
  2. 若不连通：将边加入最小生成树，累计总权值，合并两个顶点的连通分量；
  3. 若连通：跳过；
  4. 当最小生成树中的边数达到n-1时，提前终止遍历（已满足生成树条件）。

#include <iostream>
#include <vector>
#include"ArrayGraph.h"

using namespace std;

// 边的结构体：存储无向边的两个顶点和权值
struct Edge {
    int u, v, weight;  // u-起点，v-终点，weight-边权
    // 重载 < 运算符：用于sort按边权从小到大排序
    bool operator < (const Edge& other) const {
        return weight < other.weight;
    }
};

vector<int> parent; // 父节点数组
vector<int> ranks;   // 秩数组（树的高度）

// 查找：带路径压缩
int find(int x) {
    // 先找到根节点
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 路径压缩：将查找路径上所有节点直接指向根节点
    while (parent[x] != root) {
        int next = parent[x]; // 保存x的原父节点
        parent[x] = root;     // x直接指向根节点
        x = next;             // 继续处理原父节点
    }
    return root;
}

// 合并：按秩合并
bool unite(int x, int y) {
    x = find(x); // 找到x的根
    y = find(y); // 找到y的根
    if (x == y) return false; // 同一集合，直接返回
    // 按秩合并：小秩树指向大秩树
    if (ranks[x] < ranks[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        // 秩相等时，合并后根节点秩+1
        if (ranks[x] == ranks[y]) {
            ranks[x]++;
        }
    }
    return true;
}

// Kruskal算法主函数
// 返回值：最小生成树的总权值；若图不连通，返回-1
int kruskal(ArrayGraph& graph, vector<Edge>& edges) {
    int n = graph.vertexNum;
    // 步骤1：按边权从小到大排序所有边（贪心核心）
    sort(edges.begin(), edges.end());

    int totalWeight = 0;  // 最小生成树的总权值
    int edgeCount = 0;    // 已加入最小生成树的边数

    // 步骤2：依次遍历排序后的边，尝试加入最小生成树
    for (const Edge& e : edges) {
        // 若两个顶点不连通，合并并加入边
        if (unite(e.u, e.v)) {
            totalWeight += e.weight;
            edgeCount++;
            cout << "选择边：(" << graph.vertices[e.u] << ", " << graph.vertices[e.v] << ")，权值：" << e.weight << endl;
            // 最小生成树需n-1条边，提前终止
            if (edgeCount == n - 1) {
                break;
            }
        }
    }

    // 若边数不足n-1，说明图不连通，无最小生成树
    return (edgeCount == n - 1) ? totalWeight : -1;
}


// 测试案例
int main() {
    ArrayGraph graph;
    vector<Edge> edges;

    // 1. 添加顶点（A、B、C、D、E、F、G、H、I）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');

    // 2. 添加边（有权无向图）
    graph.addEdge('A','C',2);
    graph.addEdge('A','D',4);
    graph.addEdge('A','E',7);

    graph.addEdge('B','C',2);
    graph.addEdge('B','D',6);

    graph.addEdge('C','A',2);
    graph.addEdge('C','D',1);
    graph.addEdge('C','B',2);

    graph.addEdge('D','A',4);
    graph.addEdge('D','B',6);
    graph.addEdge('D','C',1);
    graph.addEdge('D','E',1);

    graph.addEdge('E','A',7);
    graph.addEdge('E','D',1);

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. 初始化并查集
    parent.resize(graph.vertexNum);
    ranks.resize(graph.vertexNum, 1); // 初始秩均为1
    for (int i = 0; i < graph.vertexNum; i++) {
        parent[i] = i; // 初始父节点为自身，自成集合
    }

    // 5. 生成边集合
    for(int i=0;i < graph.vertexNum;i++)
    {
        for(int j=0;j < graph.vertexNum;j++)
        {
            if(graph.graph[i][j]>NO_EDGE)
            {
                edges.push_back({i,j,graph.graph[i][j]});
            }
        }
    }

    // 6. 最小生成树
    int minTotal = kruskal(graph, edges);

    if (minTotal == -1) {
        cout << "图不连通，无最小生成树！" << endl;
    } else {
        cout << "最小生成树的总权值：" << minTotal << endl;
    }

    return 0;
}
        

输出结果

===== 带权邻接矩阵 =====
     A  B  C  D  E
  A  0  0  2  4  7
  B  0  0  2  6  0
  C  2  2  0  1  0
  D  4  6  1  0  1
  E  7  0  0  1  0
========================
Kruskal算法求解最小生成树过程：
选择边：(C, D)，权值：1
选择边：(D, E)，权值：1
选择边：(A, C)，权值：2
选择边：(B, C)，权值：2
最小生成树的总权值：6
            

三、Prim 算法

  将图的顶点集划分为两个部分：已选集合 U：当前已纳入最小生成树的顶点（初始时可任选一个顶点，通常选顶点 0）；未选集合 V-U：尚未纳入最小生成树的顶点。

  算法的每一步贪心选择：找到连接U 和 V-U的所有边中权值最小的那条边，将该边对应的未选顶点加入 U 集合。重复此过程，直到 U 包含图中所有顶点，此时所有选中的边即构成最小生成树。

算法分析：

设图有 n 个顶点，邻接矩阵为graph[n][n]（graph[i][j]表示顶点 i 到 j 的边权，无边时设为无穷大INF，自身到自身为 0），步骤如下：

• 初始化：选择初始顶点（如顶点 0）加入 U，即lowcost[0]=0；对其余顶点 i，lowcost[i] = graph[0][i]，adjvex[i] = 0（初始时所有未选顶点的最小边都指向顶点 0）。
• 迭代选择 n-1 条边（生成树需 n-1 条边）：
  1. 遍历所有顶点，找到未选顶点中lowcost最小的顶点 k（即lowcost[k] > 0且最小），k 是本次要加入 U 的顶点；
  2. 输出这条最小边：(adjvex[k], k)，并记录其权值；
  3. 更新辅助数组：将 k 加入 U（lowcost[k]=0），遍历所有未选顶点 j，若graph[k][j] < lowcost[j]，说明顶点 j 到 U 的最小边更新为 j→k，因此lowcost[j] = graph[k][j]，adjvex[j] = k。
• 终止条件：当 U 包含所有 n 个顶点时，迭代结束，所有输出的边构成最小生成树。

#include <iostream>
#include"ArrayGraph.h"

using namespace std;

// Prim算法：邻接矩阵版
void prim(ArrayGraph& graph) {
    int n = graph.vertexNum;
    int lowcost[MAX_VERTEX];  // 未选顶点到已选集合U的最小权值，0表示已在U中
    int adjvex[MAX_VERTEX];   // 未选顶点的最小权值边对应的U中顶点
    int total = 0;      // 最小生成树的总权值

    // 初始化，无边时设为无穷大INF，自身到自身为 0
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i == j)
            {
                //将自身至自身的距离设置为0
                graph.graph[i][j] = 0;
            }
            else if(graph.graph[i][j] == NO_EDGE)
            {
                graph.graph[i][j] = INF;//把不相连的点之间的距离设为无穷大(INF)
            }
        }
    }

    // 步骤1：初始化辅助数组，从顶点0开始（加入U）
    for (int i = 0; i < n; i++) {
        lowcost[i] = graph.graph[0][i];  // 初始时所有未选顶点的最小边指向顶点0
        adjvex[i] = 0;             // 对应U中的顶点为0
    }
    lowcost[0] = 0;  // 顶点0加入U，标记为0

    // 步骤2：迭代n-1次，选择n-1条边（生成树需n-1条边）
    for (int i = 1; i < n; i++) {
        // 2.1 找到未选顶点中lowcost最小的顶点k
        int min_val = INF;
        int k = -1;
        for (int j = 0; j < n; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min_val) {
                min_val = lowcost[j];
                k = j;
            }
        }

        // 若k=-1，说明图不连通，无最小生成树（题目保证连通时可省略）
        if (k == -1) {
            cout << "图不连通，无最小生成树！" << endl;
            return;
        }

        // 2.2 输出本次选择的最小边（adjvex[k], k）及其权值
        cout << "选择边：(" << graph.vertices[adjvex[k]] << ", " << graph.vertices[k] << ")，权值：" << min_val << endl;
        total += min_val;  // 累加总权值

        // 2.3 将顶点k加入U，更新辅助数组
        lowcost[k] = 0;  // 标记k为已选
        for (int j = 0; j < n; j++) {
            // 若j未选，且k到j的边权 < j当前到U的最小权值，则更新
            if (lowcost[j] != 0 && graph.graph[k][j] < lowcost[j]) {
                lowcost[j] = graph.graph[k][j];
                adjvex[j] = k;
            }
        }
    }

    // 输出最小生成树的总权值
    cout << "最小生成树的总权值：" << total << endl;
}


// 测试案例
int main() {
    ArrayGraph graph;

    // 1. 添加顶点（A、B、C、D、E）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');

    // 2. 添加边（有权无向图）
    graph.addEdge('A','C',2);
    graph.addEdge('A','D',4);
    graph.addEdge('A','E',7);

    graph.addEdge('B','C',2);
    graph.addEdge('B','D',6);

    graph.addEdge('C','A',2);
    graph.addEdge('C','D',1);
    graph.addEdge('C','B',2);

    graph.addEdge('D','A',4);
    graph.addEdge('D','B',6);
    graph.addEdge('D','C',1);
    graph.addEdge('D','E',1);

    graph.addEdge('E','A',7);
    graph.addEdge('E','D',1);

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. 最小生成树
    cout << "Prim算法求解最小生成树过程：" << endl;
    prim(graph);

    return 0;
}
        

输出结果

===== 带权邻接矩阵 =====
     A  B  C  D  E
  A  0  0  2  4  7
  B  0  0  2  6  0
  C  2  2  0  1  0
  D  4  6  1  0  1
  E  7  0  0  1  0
========================
Prim算法求解最小生成树过程：
选择边：(A, C)，权值：2
选择边：(C, D)，权值：1
选择边：(D, E)，权值：1
选择边：(C, B)，权值：2
最小生成树的总权值：6
            

四、典型应用场景

Prim 算法：首选「稠密图」

1. 路网规划（少量城市，任意两地间几乎都有道路）；
2. 集成电路布线（少量元器件，引脚间多连接）；
3. 小规模网格图计算（如 n≤2000 的网格顶点连接）。

Kruskal 算法：首选「稀疏图」

1. 社交网络（上亿用户，每人仅几百个好友，边数远小于顶点平方）；
2. 通信网络（大量基站，仅相邻基站间有连接）；
3. 大规模地图导航（海量地点，仅相邻地点间有道路）；
4. 分布式网络拓扑设计（大量节点，仅点对点连接）。